package com.yww.leetcode.linkedlist;

import com.yww.leetcode.common.ListNode;

import java.util.Random;

/**
 * @author yww
 * @description 82. 删除排序链表中的重复元素 II
 * @since 2024/2/2 15:01
 */
public class DeleteDuplicates82 {
    // 给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。
    // 返回 已排序的链表 。
    public ListNode deleteDuplicates(ListNode head) {
        int i = new Random().nextInt();
        if (i % 2 == 0) {
            return del01(head);
        } else {
            return del02(head);
        }
    }

    // 方法1：递归删除法
    private static ListNode del01(ListNode cur) {
        if (cur == null || cur.next == null) {
            return cur;
        }
        // 如果当前节点和下个节点值相等
        if (cur.val == cur.next.val) {
            // 循环往下找到第一个不相等的节点
            ListNode x = cur.next.next;
            while (x != null && x.val == cur.val) {
                x = x.next;
            }
            // 找到了val不相等的节点
            // 跳过当前节点和下一个节点，返回递归处理结果
            return del01(x);
        } else {
            // 递归更新下一个节点
            cur.next = del01(cur.next);
            // 返回当前节点
            return cur;
        }
    }

    private static ListNode del02(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 创建一个哨兵
        ListNode sentinel = new ListNode(-1, head);
        // 指向删除节点的前驱
        ListNode p1 = sentinel;
        // 指向删除节点1
        ListNode p2;
        // 指向删除节点2
        ListNode p3;

        // p2,p3后移
        while ((p2 = p1.next) != null && (p3 = p2.next) != null) {
            // 如果p2,p3节点值相等，着p3往后移动直到第一个不相等的节点
            if (p2.val == p3.val) {
                while (p3 != null && p3.val == p2.val) {
                    // p3后移
                    p3 = p3.next;
                }
                // 前驱p1跳过这些重复的节点
                p1.next = p3;
            } else {
                // p1后移
                p1 = p1.next;
            }
        }
        return sentinel.next;
    }
}
